package Top200;

/**
 * @author zhangmin
 * @create 2022-02-27 14:04
 */
public class numDecodings91 {
    public int numDecodings(String s) {
        int n=s.length();
        int[] dp=new int[n];
        if (s.charAt(0)=='0') return 0;
        dp[0]=1;
        for (int i = 1; i < n; i++) {
            int num=(s.charAt(i-1)-'0')*10+(s.charAt(i)-'0');
            if (s.charAt(i)=='0'){
                //只能与前一位一起编码
                if (num>=10&&num<=26){
                    dp[i]=(i-2>0?dp[i-2]:1);
                }
                continue;
            }
            if (num>=10&&num<=26){
                //可以和前一位一起组成一个编码
                dp[i]=(i-2>0?dp[i-2]:1)+dp[i-1];
            }else {
                dp[i]=dp[i-1];
            }
        }
        return dp[n-1];
    }
}
